import java.util.ArrayList;
import java.util.List;
import java.util.Random;

//fx = 21.5 + x1 * sin(4pai * x1) + x2 * sin(20pai * x2)
//  -3.0 <= x1 <= 12.1
//  4.1 <= x2 <= 5.8
//  如结果精确到五位小数，则15.1*10^5,1.7*10^5
//  2^20 < 15.1*10^5 < 2^21
//  2^17 < 1.1*10^5 < 2^18
//  x1 = -3.0 + 15.1 * (二进制转十进制/2^21 - 1)
//  x2 = 4.1 + 1.7 * (二进制转十进制/2^18 - 1)

public class GA {
    private static final int Gene_length_x1 = 21; //x1需要的基因位数
    private static final int Gene_length_x2 = 18; //x2需要的基因位数
    private static final int Population_size = 50; //种群个体最大个数
    private static final int max_generations = 100; //最大迭代次数
    private static final double crossover_ = 0.7; //交叉概率
    private static final double mutation_ = 0.01; //变异概率

    private static final double x1_min = -3.0;
    private static final double x1_max = 12.1;
    private static final double x2_min = 4.1;
    private static final double x2_max = 5.8;

    //个体类
    static class individual {
        String gene_x1;
        String gene_x2;
        double x1;
        double x2;
        double fitness;

        public individual(String gene_x1,String gene_x2){
            this.gene_x1 = gene_x1;
            this.gene_x2 = gene_x2;
            decode();
            calculateFitness();
        }

        //解码函数，先二进制转十进制，再转为区间数
        private void decode(){
            long x1Int = Integer.parseInt(gene_x1,2);
            this.x1 = x1_min + (x1_max - x1_min) * x1Int / (Math.pow(2,Gene_length_x1)-1);

            long x2Int = Integer.parseInt(gene_x2,2);
            this.x2 = x2_min + (x2_max - x2_min) * x2Int / (Math.pow(2,Gene_length_x2)-1);
        }

        //适应度计算函数，直接用函数值代替
        private void calculateFitness(){
            double term1 = x1 * Math.sin(4 * Math.PI * x1);
            double term2 = x2 * Math.sin(20 * Math.PI * x2);
            this.fitness = 21.5 + term1 +term2;
        }
    }

    private static final Random random = new Random();

    //初始化种群
    public static List<individual>init() {
        List<individual> population = new ArrayList<>();

        //每次循环生成一组x1，x2，直接生成x1，x2的基因，采取随机数插入每一个二进制位
        for(int i=0;i<Population_size;i++){
            StringBuilder chromosome_x1 = new StringBuilder();
            for(int j=0;j<Gene_length_x1;j++){
                chromosome_x1.append(random.nextInt(2));
            }

            StringBuilder chromosome_x2 = new StringBuilder();
            for(int j=0;j<Gene_length_x2;j++){
                chromosome_x2.append(random.nextInt(2));
            }

            population.add(new individual(chromosome_x1.toString(), chromosome_x2.toString()));
        }
        return population;
    }

    //选择函数
    public static List<individual> select(List<individual> population) {
        List<individual> newPopulation = new ArrayList<>();

        double totalFitness = population.stream().mapToDouble(ind -> ind.fitness).sum();
        for(int i=0;i<Population_size;i++) {
            double r = random.nextDouble() * totalFitness;
            double sum = 0;
            for(individual ind : population) {
                sum += ind.fitness;
                if(sum > r) {
                    newPopulation.add(new individual(ind.gene_x1, ind.gene_x2));
                    break;
                }
            }
        }
        return newPopulation;
    }

    //交叉函数,采取两点交叉，随机生成一个交叉点，进行x1互换生成两条与之前不同的x1，x2同理
    public static List<individual> crossover(List<individual> population) {
        List<individual> newPopulation = new ArrayList<>();

        for(int i=0;i<Population_size;i += 2) {
            individual ind1 = population.get(i);
            individual ind2 = population.get(i+1);

            //先交叉x1
            String newGene_x1_1 = ind1.gene_x1;
            String newGene_x1_2 = ind2.gene_x1;
            //（0.7概率交叉，那么轮盘里70%的部分都是要交叉，只要生成数小于crossover_，即代表落在 70%的部分）
            if(random.nextDouble() < crossover_) {
                int crossPoint_x1 = random.nextInt(Gene_length_x1);
                newGene_x1_1 = ind1.gene_x1.substring(0,crossPoint_x1) + ind2.gene_x1.substring(crossPoint_x1);
                newGene_x1_2 = ind2.gene_x1.substring(0,crossPoint_x1) + ind1.gene_x1.substring(crossPoint_x1);
            }

            //再交叉x2，交叉概率同x1
            String newGene_x2_1 = ind1.gene_x2;
            String newGene_x2_2 = ind2.gene_x2;
            if(random.nextDouble() < crossover_) {
                int crossPoint_x2 = random.nextInt(Gene_length_x2);
                newGene_x2_1 = ind1.gene_x2.substring(0,crossPoint_x2) + ind2.gene_x2.substring(crossPoint_x2);
                newGene_x2_2 = ind2.gene_x2.substring(0,crossPoint_x2) + ind1.gene_x2.substring(crossPoint_x2);
            }

            //将交叉后的个体加回去
            newPopulation.add(new individual(newGene_x1_1,newGene_x2_1));
            newPopulation.add(new individual(newGene_x1_2,newGene_x2_2));
        }
        return newPopulation;
    }

    //变异函数,注意变异是针对每一位而言，而不是每一条染色体
    public static List<individual> mutation(List<individual> population) {
        List<individual> newPopulation = new ArrayList<>();

        for(individual ind : population) {
            StringBuilder chromosome_x1 = new StringBuilder(ind.gene_x1);
            for(int i=0;i<Gene_length_x1;i++) {
                if(random.nextDouble() < mutation_) {
                    //因为该位触发变异操作，直接获取当前位，是0变1，是1变0
                    chromosome_x1.setCharAt(i, chromosome_x1.charAt(i) == '0' ? '1' : '0');
                }
            }

            StringBuilder chromosome_x2 = new StringBuilder(ind.gene_x2);
            for(int i=0;i<Gene_length_x2;i++) {
                if(random.nextDouble() < mutation_) {
                    //同x1
                    chromosome_x2.setCharAt(i, chromosome_x2.charAt(i) == '0' ? '1' : '0');
                }
            }

            newPopulation.add(new individual(chromosome_x1.toString(),chromosome_x2.toString()));
        }
        return newPopulation;
    }

    //获取最优个体,计算适应度，最大的替换即可
    public static individual getBestInd(List<individual> population) {
        individual best_ind = population.get(0);
        for(individual ind : population) {
            if(ind.fitness > best_ind.fitness) {
                best_ind = ind;
            }
        }
        return best_ind;
    }

    public static void main(String []args) {
        List<individual> population = init();
        for(int gen=0;gen<max_generations;gen++) {
            population = select(population);
            population = crossover(population);
            population = mutation(population);
            individual best_ind = getBestInd(population);

            System.out.println("第" + (gen + 1) + "次迭代最优解为");
            System.out.printf("x1 = %.5f; x2 = %.5f; fx = %.5f%n", best_ind.x1, best_ind.x2, best_ind.fitness);
        }

    }
}
